package com.computer.fundamentals.datastructure;

import com.computer.util.Constant;
import com.computer.util.UniversalMethod;


public class MaxHeap {

    /**
     * 上浮
     */
    public void shiftUp(int[] heap, int endIdx) {
        if (heap == null) {
            throw new RuntimeException(Constant.HEAP_IS_NULL);
        }
        int endVal = heap[endIdx];
        while (endIdx > 0 && heap[(endIdx - 1) / 2] < endVal) {
            heap[endIdx] = heap[(endIdx - 1) / 2];
            endIdx = (endIdx - 1) / 2;
        }
        heap[endIdx] = endVal;
    }

    /**
     * 下沉
     */
    public void shiftDown(int[] heap, int startIdx, int endIdx) {
        if (heap == null || heap.length == 0) {
            throw new RuntimeException(Constant.HEAP_IS_NULL_AND_LENGTH_ZERO);
        }
        int startVal = heap[startIdx];
        while (startIdx * 2 + 1 <= endIdx) {
            int child = startIdx * 2 + 1;
            if (child + 1 <= endIdx && heap[child] < heap[child+1]) {
                child++;
            }
            if (heap[child] > startVal) {
                heap[startIdx] = heap[child];
                startIdx = child;
            }else {
                break;
            }
        }
        heap[startIdx] = startVal;
    }

    /**
     * 堆排序
     */
    public int[] heapSort(int[] array) {
        int[] heap = new int[array.length];
        for (int i = 0;i < array.length;i++) {
            heap[i] = array[i];
            shiftUp(heap, i);
        }

        int endIdx = heap.length-1;
        while (endIdx > 0) {
            int tmp = heap[0];
            heap[0] = heap[endIdx];
            heap[endIdx] = tmp;
            shiftDown(heap, 0, --endIdx);
        }

        return heap;
    }

    /**
     * 测试
     */
    public static void main(String[] args) {
        int[] array = UniversalMethod.createArray(Constant.DEFAULT_ARRAY_LENGTH);
        MaxHeap maxHeap = new MaxHeap();

        System.out.println("---------------原数组---------------");
        UniversalMethod.printArray(array);
        System.out.println("\n");

        System.out.println("---------------排序数组---------------");
        int[] sortedArray = maxHeap.heapSort(array);
        UniversalMethod.printArray(sortedArray);
    }
}
